Information shared between government agencies, and between government agencies and contractors, is often sensitive. Such information is generally classified according to guidelines established by the government agency involved. When such classified information requires transmission between secured facilities (e.g., phone conversations, FAXes, or transmission of computer files), a means must be exercised to prevent the information from being intercepted. Also, communications between individuals often include personal or business related content that that the individuals intend to maintain as private.
The National Institute of Standards and Technology has established the Advanced Encryption Standard (AES) as the approved cryptographic algorithm for such transmission. Copies of the AES are available from the National Technical Information Service (NTIS), 5285 Port Royal Road, Springfield, Va. 22161.
The AES specifies the Rijndael algorithm, a symmetric block cipher that can process data blocks of 128 bits, using cipher keys with lengths of 128, 192, and 256 bits. The input and output for the AES algorithm each consist of sequences of 128 bits (digits with values of 0 or 1). The basic unit for processing in the AES algorithm is a byte. The input, output and Cipher Key bit sequences are processed as arrays of bytes that are formed by dividing these sequences into groups of eight contiguous bits to form the arrays of bytes.
All byte values in the AES algorithm will be presented as the concatenation of its individual bit values (0 or 1) between braces in the order {b7, b6, b5, b4, b3, b2, b1, b0}. These bytes are interpreted as finite field elements using a polynomial representation:                     b        7            ⁢              x        7              +                  b        6            ⁢              x        6              +                  b        5            ⁢              x        5              +                  b        4            ⁢              x        4              +                  b        3            ⁢              x        3              +                  b        2            ⁢              x        2              +                  b        1            ⁢      x        +          b      0        =            ∑              i        =        0            7        ⁢                  ⁢                  b        i            ⁢                        x          i                .            For example, {01100011} identifies the specific finite field element x6+x5+x+1.
Internally, the AES algorithm's operations are performed on a two-dimensional array of bytes called the State array. The State array consists of four rows of bytes, each containing four bytes. At the start of the Cipher, or of the Inverse Cipher, the input (a two dimensional array of bytes) is copied into the State array. The Cipher or Inverse Cipher operations are then conducted on this State array, after which its final value is copied to the output (a two dimensional array of bytes).
All bytes in the AES algorithm are interpreted as finite field elements. Finite field elements can be added and multiplied, but these operations are different from those used for normal numbers.
In the polynomial representation, multiplication (denoted by ·) in a Galois field (256), i.e., GF(28), corresponds with the multiplication of polynomials modulo m(x), where m(x) is an irreducible polynomial of degree 8. A polynomial is irreducible if its only divisors are one and itself. For the AES algorithm, this irreducible polynomial is:m(x)=x8+x4+x3+x+1,or 1{1b} in hexadecimal notation.
For example, {57}·{83}={c1}, because                                           (                                          x                6                            +                              x                4                            +                              x                2                            +              x              +              1                        )                    ⁢                      (                                          x                7                            +              x              +              1                        )                          =                ⁢                              x            13                    +                      x            11                    +                      x            9                    +                      x            8                    +                      x            7                    +                                                ⁢                              x            7                    +                      x            5                    +                      x            3                    +                      x            2                    +          x          +                                                ⁢                              x            6                    +                      x            4                    +                      x            2                    +          x          +          1                                        =                ⁢                              x            13                    +                      x            11                    +                      x            9                    +                      x            8                    +                      x            6                    +                      x            5                    +                      x            4                    +                      x            3                    +                      1            ⁢                                                  ⁢            and                                                          ⁢                              x            13                    +                      x            11                    +                      x            9                    +                      x            8                    +                      x            6                    +                      x            5                    +                      x            4                    +                      x            3                    +                                                ⁢                  1          ⁢                                          ⁢          modulo          ⁢                                          ⁢                      (                                          x                8                            +                              x                4                            +                              x                3                            +              x              +              1                        )                                                  =                ⁢                              x            7                    +                      x            6                    +          1.                    
The modular reduction by m(x) ensures that the result will be a binary polynomial of degree less than 8, and thus can be represented by a byte. However, there is no simple operation at the byte level that corresponds to this multiplication.
The multiplication defined above is associative, and the element {01} is the multiplicative identity. For any non-zero binary polynomial b(x) of degree less than 8, the multiplicative inverse of b(x), denoted b−1(x), can be found as follows: the extended Euclidean algorithm described in the CRC Press Handbook of Applied Cryptography, published in 1997, on pages 81–83, is used to compute polynomials a(x) and c(x) such that:b(x)a(x)+m(x)c(x)=1.Hence, a(x)·b(x)mod m(x)=1, which means:b−1(x)=a(x)mod m(x).Moreover, it holds that:a(x)·(b(x)+c(x))=a(x)·b(x)+a(x)·c(x).
It follows that the set of 256 possible byte values, with XOR used as addition and the multiplication defined as above, has the structure of the finite field GF(28).
The Cipher is comprised of four individual transformations: SubBytes, ShiftRows, MixColumns, and AddRoundKey. The Mixcolumns transform includes multiplication over a GF(28), which multiplication is described above. The Inverse Cipher similarly includes four individual inverse transformations: InvShiftRows, InvSubBytes, InvMixColumns, and AddRoundKey, wherein InvMixColumns also includes multiplication over a GF(28). Each call to MixColumns and to InvMixColumns results in sixteen such multiplications. Further, each Cipher or Inverse Cipher operation requires 9, 11, or 13 calls to MixColumns or InvMixColumns respectively, where the number of calls depends on the key length.
As described above, multiplication over the GF(28) requires the multiplication of two polynomials, followed by a modulo operation, which is Mips intensive. Alternatively, the multiplication over the GF(28) may be performed by table lookup which is much less Mips intensive. Generally such table would comprise a table size of 256×256 which equals 65,536 elements. However, in the case of the AES algorithm, one term in the multiplication is limited to 6 values, so the table size is reduced to 6×256 (i.e., 1536 elements.) However, even reducing the table size to 1536 elements places a burden on memory space.
What is needed is a way to avoid the Mips intensive actual multiplication without placing a burden on memory space.